import java.util.ArrayList;

import org.apache.commons.lang.ArrayUtils;


public class Ex7_5 {

	public Ex7_5() {}

	public static void main(String[] args) {
		Ex7_5 ex = new Ex7_5();
		ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\dataset_79_12.txt");
		String v = inputs.get(0);
		String w = inputs.get(1);		
		//ex.getScore(v, w);
		ex.getMiddleNode(v,w);
	}
	
	
	private void getMiddleNode(String v,String w) {
		
		Integer[] forw = getScore(v,w,w.length()/2 + 1)[1];
		Integer[] forwPrev = getScore(v,w,w.length()/2 + 1)[0];		
		Integer[][] back = getScore(new StringBuilder(v).reverse().toString(),
				new StringBuilder(w).reverse().toString(),w.length()/2 + 1);
		Integer[] backMiddle = back[1];
		Integer[] backMiddlePrev = back[0];		
		ArrayUtils.reverse(backMiddle);
		ArrayUtils.reverse(backMiddlePrev);
		
		Integer i = getMax(forwPrev,backMiddle);
		Integer i_next =  getMax(forw,backMiddlePrev);
		
		Integer[][] nodes = new Integer[2][2];
		nodes[0][0] = i;
		nodes[0][1] = w.length()/2;
		nodes[1][0] = i_next;
		nodes[1][1] = w.length()/2 + 1;
		
		System.out.print("("+ nodes[0][0] + ", " + nodes[0][1]+ ")");
		System.out.print(" ");
		System.out.print("("+ nodes[1][0] + ", " + nodes[1][1] + ")");
		
		
	}

	private Integer getMax(Integer[] array1, Integer[] array2) {		
		Integer maxValue = -9999;
		Integer index = -1;
		if (array1.length != array2.length) {
			return null;
		}
		for (int i=0;i<array1.length;i++) {
			Integer sumVal = array1[i] + array2[i];
			if (sumVal > maxValue) {
				index = i;
				maxValue = sumVal;
			}
		}
		return index;
	}
	
	private Integer[][] getScore(String v, String w, Integer col) {
		Integer sigma = 5;
		String blosum62 = "ACDEFGHIKLMNPQRSTVWY";		
		Integer[][] blosumMatrix = 
				Utils.readMatrix("C:\\Users\\josemfer\\Downloads\\BLOSUM62.txt");
		
		Integer[] prevCol = new Integer[v.length()+1];
		Integer[] thisCol = new Integer[v.length()+1];		
		for (int j=0;j<=col;j++) {		
			prevCol = thisCol.clone();
			for (int i=0;i<=v.length();i++) {
				//System.out.println("i=" + i + "   j=" + j);
				if (j==0) {
					thisCol[i] = -i*sigma;							
				} else {
					if (i==0) {
						thisCol[i] = -j*sigma;								
					} else {						
						Integer up = thisCol[i-1] - sigma;
						Integer left = prevCol[i] - sigma;
						// get diagonal value
						char vi = v.charAt(i-1);
						char wj = w.charAt(j-1);
						Integer diag = prevCol[i-1] + 
								blosumMatrix[blosum62.indexOf(vi)][blosum62.indexOf(wj)];
						thisCol[i] = Utils.max(new Integer[]{up,left,diag});						
					}					
				}				
			}						
		}		
		Integer[][] matrix = new Integer[2][prevCol.length];
		matrix[0] = prevCol;
		matrix[1] = thisCol;		
		return matrix;	
	} // end getScore

} // end class
